串的定义

串（string）（或字符串）是由零个或多个字符组成的有限序列，一般记为

s=“a1a2 … an”(n≥0)

其中，s是串的名，用双引号括起来的字符序列是串的值；ai(1≤i≤n)可以是字母、数字或其他字符；串中字符的数目n称为串的长度。零个字符的串称为空串（null string），其长度为零。

串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。

由一个或多个空格组成的串“ ”称为空格串（blank string，请注意：此处不是空串），其长度为串中空格字符的个数。为了清楚起见，以后我们用符号“Ø”来表示“空串”。

案例引入

tips：案例4.1：病毒感染检测。

---

医学研究者最近发现了某些新病毒，通过对这些病毒的分析，得知它们的DNA序列都是环状的。现在研究者已收集了大量的病毒DNA和人的DNA数据，想快速检测出这些人是否感染了相应的病毒。为了方便研究，研究者将人的DNA和病毒DNA均表示成由一些字母组成的字符串序列，然后检测某种病毒DNA序列是否在患者的DNA序列中出现过，如果出现过，则此人感染了该病毒，否则没有感染。例如，假设病毒的DNA序列为baa，患者1的DNA序列为aaabbba，则感染，患者2的DNA序列为babbba，则未感染。（注意，人的DNA序列是线性的，而病毒的DNA序列是环状的）
研究者将待检测的数据保存在一个文本文件中，文件格式和内容规定如下（图4.1截取了部分数据）。

文件有num+1行，第一行有一个整数num，表示有num个待检测的任务（num<=300）。
接下来每行i（2<=i<=num+1）对应一个任务，每行有两个数据，用空格分隔，第一个数据表示病毒的dna序列（长度<=6000），第二个数据表示人的dna序列（长度<=10000）。
要求将检测结果输出到文件中，文件中包括num行，每行有三个数据，用空格分隔，前两个数据分别表示输入文件中对应病毒的DNA序列人的DNA序列，如果该人感染了对应的病毒，该行第三个数据则为“YES”，否则为“NO”。图4.1数据对应的输出结果如图4.2所示。

这个案例中要处理的操作对象便是字符串，将病毒的DNA序列看作是子串，患者的DNA序列看作是主串，检测任务的实质就是看子串是否在主串中出现过，即4.3.3小节讨论的字符串的模式匹配算法。但因为此案例中病毒的DNA序列是环状的，这样需要对传统模式匹配算法进行改进。案例的具体分析与实现将在4.6节给出。

---

4.3 串的类型定义、存储结构及其运算

4.3.1 串的抽象类型定义

ADT String{
  数据对象：D={ai|ai∈CharacterSet,i=1,2,…,n,n≥0}
  数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}
  基本操作：
    StrAssign(&T,chars)    
      初始条件：chars是字符串常量。    
      操作结果：生成一个其值等于chars的串T。    
    StrCopy(&T,S)    
      初始条件：串S存在。    
      操作结果：由串S复制得串T。    
    StrEmpty(S)    
      初始条件：串S存在。    
      操作结果：若S为空串，则返回true，否则返回false。    
    StrCompare(S,T)    
      初始条件：串S和T存在。    
      操作结果：若S>T，则返回值>0；若S=T，则返回值＝0；若S<T，则返回值<0。  
    StrLength(S)    
      初始条件：串S存在。    
      操作结果：返回S的元素个数，称为串的长度。    
    ClearString(&S)    
      初始条件：串S存在。    
      操作结果：将S清为空串。    
    Concat(&T,S1,S2)    
      初始条件：串S1和S2存在。    
      操作结果：用T返回由S1和S2联接而成的新串。    
    SubString(&Sub,S,pos,len)
      初始条件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。  
      操作结果：用Sub返回串S的第pos个字符起长度为len的子串。
    Index(S,T,pos)    
      初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。 
      操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。  
    Replace(&S,T,V)  
      初始条件：串S，T和V存在，T是非空串。    
      操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。    
    StrInsert(&S,pos,T)    
      初始条件：串S和T存在，1≤pos≤StrLength(S)+1。    
      操作结果：在串S的第pos个字符之前插入串T。    
    StrDelete(&S,pos,len)    
      初始条件：串S存在，1≤pos≤StrLength(S)-len+1。    
      操作结果：从串S中删除第pos个字符起长度为len的子串。    
    DestroyString(&S)    
      初始条件：串S存在。    
      操作结果：串S被销毁。    
}ADT String

4.3.2 串的存储结构

串的顺序存储

//- - - - - 串的定长顺序存储结构- - - - -
#define MAXLEN 255                      //串的最大长度
typedef struct{
   char ch[MAXLEN+1];                   //存储串的一维数组
   int length;                          //串的当前长度
}SString;